package sort;

/**
 * 七大排序
 * @author yuisama
 * @date 2022/03/03 20:51
 **/
public class SevenSort {
    // 选择排序
    public static void selectionSort(int[] arr) {
        // 最开始，无序区间[0...n]  有序区间[]
        // 当无序区间只剩下一个元素时，整个集合已经有序
        for (int i = 0; i < arr.length - 1; i++) {
            // min变量存储了当前的最小值索引
            int min = i;
            // 从剩下的元素中选择最小值
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            // min这个索引一定对应了当前无序区间中找到的最小值索引，换到无序区间最前面i
            swap(arr,min,i);
        }
    }

    // 双向选择排序
    public static void selectionSortOP(int[] arr) {
        int low = 0;
        int high = arr.length - 1;
        // low = high，无序区间只剩下一个元素，整个数组已经有序
        while (low <= high) {
            int min = low;
            int max = low;
            for (int i = low + 1; i <= high; i++) {
                if (arr[i] < arr[min]) {
                    min = i;
                }
                if (arr[i] > arr[max]) {
                    max = i;
                }
            }
            // min索引一定是当前无序区间的最小值索引，与low交换位置
            swap(arr,low,min);
            if (max == low) {
                // 最大值已经被换到min这个位置
                max = min;
            }
            swap(arr,max,high);
            low += 1;
            high -= 1;
        }
    }

    public static void mergeSort(int[] arr) {
        mergeSortInternal(arr,0,arr.length - 1);
    }

    /**
     * 在arr[l...r]进行归并排序,整个arr经过函数后就是一个已经有序的数组
     * @param arr
     * @param l
     * @param r
     */
    private static void mergeSortInternal(int[] arr, int l, int r) {
        if (r - l <= 15) {
            // 2.小区间直接使用插入排序
            insertionSort(arr,l,r);
            return;
        }
        int mid = l + ((r - l) >> 1);
        // 将原数组拆分为左右两个小区间，分别递归进行归并排序
        // 走完这个函数之后 arr[l..mid]已经有序
        mergeSortInternal(arr,l,mid);
        // 走完这个函数之后 arr[mid + 1..r]已经有序
        mergeSortInternal(arr,mid + 1,r);
        // 1.只有左右两个子区间还有先后顺序不同时才merge
        if (arr[mid] > arr[mid + 1]) {
            merge(arr,l,mid,r);
        }
    }

    private static void insertionSort(int[] arr, int l, int r) {
        for (int i = l + 1; i <= r; i++) {
            for (int j = i; j > l && arr[j] < arr[j - 1]; j--) {
                swap(arr,j,j - 1);
            }
        }
    }



    private static void merge(int[] arr, int l, int mid, int r) {
        // 先创建一个新的临时数组aux
        int[] aux = new int[r - l + 1];
        // 将arr元素值拷贝到aux上
        for (int i = 0; i < aux.length; i++) {
            aux[i] = arr[i + l];
        }
        // i就是左侧小数组的开始索引
        int i = l;
        // j就是右侧小数组的开始索引
        int j = mid + 1;
        // k表示当前正在合并的原数组的索引下标
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                // 左侧区间已经被处理完毕，只需要将右侧区间的值拷贝原数组即可
                arr[k] = aux[j - l];
                j ++;
            }else if (j > r) {
                // 右侧区间已经被处理完毕，只需要将左侧区间的值拷贝到原数组即可
                arr[k] = aux[i - l];
                i ++;
            }else if (aux[i - l] <= aux[j - l]) {
                // 此时左侧区间的元素值较小，相等元素放在左区间，保证稳定性
                arr[k] = aux[i - l];
                i ++;
            }else {
                // 右侧区间的元素值较小
                arr[k] = aux[j - l];
                j ++;
            }
        }
    }


    public static  void shellSort(int[] arr){
        int gap= arr.length>>1;
        while (gap>1){
            insertionSortGap(arr,gap);
            gap=gap>>1;
        }
        insertionSort(arr);
    }

    private static void insertionSortGap(int[] arr, int gap) {
        for (int i = gap; i<arr.length ; i++) {
            for (int j = i; j-gap>=0&& arr[j]<arr[j-gap]; j-=gap) {
                swap(arr,j,j-gap);
            }
        }
    }

    // 直接插入排序
    // 每次从无序区间中拿第一个值插入到已经排序区间的合适位置，直到整个数组有序
    public static void insertionSort(int[] arr) {
        // 已排序区间[0,i)
        // 待排序区间[i...n]
        for (int i = 1; i < arr.length; i++) {
            // 待排序区间的第一个元素arr[i]
            // 从待排序区间的第一个元素向前看，找到合适的插入位置
//            for (int j = i; j > 0; j--) {
//                // arr[j - 1]已排序区间的最后一个元素
//                if (arr[j] >= arr[j - 1]) {
//                    // 相等我们也不交换，保证稳定性
//                    // 此时说明arr[j] 》 已排序区间的最大值，arr[j]已经有序了~~直接下次循环
//                    break;
//                }else {
//                    swap(arr,j,j - 1);
//                }
//            }
            for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
                swap(arr,j,j - 1);
            }
        }
    }

    public static void insertionSortBS(int[] arr) {
        // 有序区间[0..i)
        // 无序区间[i...n]
        for (int i = 1; i < arr.length; i++) {
            int val = arr[i];
            int left = 0;
            int right = i;
            while (left < right) {
//                int mid = left + ((right - left) >> 1);
                int mid = (left + right) >> 1;
                if (val < arr[mid]) {
                    right = mid;
                }else {
                    // val >= arr[mid]
                    left = mid + 1;
                }
            }
            // 搬移left..i的元素
            for (int j = i; j > left; j--) {
                arr[j] = arr[j - 1];
            }
            // left就是val插入的位置
            arr[left] = val;
        }
    }


    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean isSwaped = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr,j,j + 1);
                    isSwaped = true;
                }
            }
            if (!isSwaped) {
                break;
            }
        }
    }

    public static void heapSort(int[] arr) {
        // 1.先将arr进行heapify调整为最大堆
        // 从最后一个非叶子节点开始进行siftDown操作
        for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
            siftDown(arr,i,arr.length);
        }
        // 此时arr就被我调整为最大堆
        for (int i = arr.length - 1; i > 0; i--) {
            // arr[0] 堆顶元素，就是当前堆的最大值
            swap(arr,0,i);
            siftDown(arr,0,i);
        }
    }

    /**
     * 元素下沉操作
     * @param arr
     * @param i 当前要下沉的索引
     * @param length 数组长度
     */
    private static void siftDown(int[] arr, int i, int length) {
        while (2 * i + 1 < length) {
            int j = (i << 1) + 1;
            if (j + 1 < length && arr[j + 1] > arr[j]) {
                j = j + 1;
            }
            // j就是左右子树的最大值
            if (arr[i] > arr[j]) {
                // 下沉结束
                break;
            }else {
                swap(arr,i,j);
                i = j;
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}